//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "polarphp/ast/AstPrinter.h"
#include "polarphp/ast/Decl.h"
#include "polarphp/ast/NameLookup.h"
#include "polarphp/basic/SourceMgr.h"
#include "polarphp/frontend/Frontend.h"
#include "polarphp/frontend/PrintingDiagnosticConsumer.h"
#include "polarphp/ide/CommentConversion.h"
#include "polarphp/ide/Utils.h"
#include "polarphp/markup/XMLUtils.h"
#include "polarphp/global/Subsystems.h"

#include "clang/AST/AstContext.h"
#include "clang/AST/DeclObjC.h"
#include "clang/Basic/Module.h"
#include "clang/Index/USRGeneration.h"
#include "clang/Lex/Lexer.h"
#include "clang/Basic/CharInfo.h"

#include "llvm/Support/MemoryBuffer.h"

#include <numeric>

using namespace polar;
using namespace polar::ide;
using namespace polar::llparser;

Optional<std::pair<unsigned, unsigned>>
polar::ide::parseLineCol(StringRef LineCol) {
   unsigned Line, Col;
   size_t ColonIdx = LineCol.find(':');
   if (ColonIdx == StringRef::npos) {
      llvm::errs() << "wrong pos format, it should be '<line>:<column>'\n";
      return None;
   }
   if (LineCol.substr(0, ColonIdx).getAsInteger(10, Line)) {
      llvm::errs() << "wrong pos format, it should be '<line>:<column>'\n";
      return None;
   }
   if (LineCol.substr(ColonIdx+1).getAsInteger(10, Col)) {
      llvm::errs() << "wrong pos format, it should be '<line>:<column>'\n";
      return None;
   }

   if (Line == 0 || Col == 0) {
      llvm::errs() << "wrong pos format, line/col should start from 1\n";
      return None;
   }

   return std::make_pair(Line, Col);
}

void XMLEscapingPrinter::printText(StringRef Text) {
   polar::markup::appendWithXMLEscaping(OS, Text);
}

void XMLEscapingPrinter::printXML(StringRef Text) {
   OS << Text;
}

SourceManager &NameMatcher::getSourceMgr() const {
   return SrcFile.getAstContext().SourceMgr;
}

std::vector<ResolvedLoc> NameMatcher::resolve(ArrayRef<UnresolvedLoc> Locs, ArrayRef<Token> Tokens) {

   // Note the original indices and sort them in reverse source order
   std::vector<size_t> MapToOriginalIndex(Locs.size());
   std::iota(MapToOriginalIndex.begin(), MapToOriginalIndex.end(), 0);
   std::sort(MapToOriginalIndex.begin(), MapToOriginalIndex.end(),
             [this, Locs](size_t first, size_t second) {
                return first != second && !getSourceMgr()
                   .isBeforeInBuffer(Locs[first].Loc, Locs[second].Loc);
             });

   // Add the locs themselves
   LocsToResolve.clear();
   std::transform(MapToOriginalIndex.begin(), MapToOriginalIndex.end(),
                  std::back_inserter(LocsToResolve),
                  [&](size_t index){ return Locs[index]; });

   InactiveConfigRegionNestings = 0;
   SelectorNestings = 0;
   TokensToCheck = Tokens;
   ResolvedLocs.clear();
   SrcFile.walk(*this);
   checkComments();

   // handle any unresolved locs past the end of the last AST node or comment
   std::vector<ResolvedLoc> Remaining(Locs.size() - ResolvedLocs.size(), {
      AstWalker::ParentTy(), CharSourceRange(), {}, LabelRangeType::None,
      /*isActice*/true, /*isInSelector*/false});
   ResolvedLocs.insert(ResolvedLocs.end(), Remaining.begin(), Remaining.end());

   // return in the original order
   std::vector<ResolvedLoc> Ordered(ResolvedLocs.size());
   for(size_t Index = 0; Index < ResolvedLocs.size(); ++Index) {
      size_t Flipped = ResolvedLocs.size() - 1 - Index;
      Ordered[MapToOriginalIndex[Flipped]] = ResolvedLocs[Index];
   }
   return Ordered;
}

static std::vector<CharSourceRange> getLabelRanges(const ParameterList* List,
                                                   const SourceManager &SM) {
   std::vector<CharSourceRange> LabelRanges;
   for (ParamDecl *Param: *List) {
      if (Param->isImplicit())
         continue;

      SourceLoc NameLoc = Param->getArgumentNameLoc();
      SourceLoc ParamLoc = Param->getNameLoc();
      size_t NameLength;
      if (NameLoc.isValid()) {
         LabelRanges.push_back(Lexer::getCharSourceRangeFromSourceRange(
            SM, SourceRange(NameLoc, ParamLoc)));
      } else {
         NameLoc = ParamLoc;
         NameLength = Param->getNameStr().size();
         LabelRanges.push_back(CharSourceRange(NameLoc, NameLength));
      }
   }
   return LabelRanges;
}

static std::vector<CharSourceRange> getEnumParamListInfo(SourceManager &SM,
                                                         ParameterList *PL) {
   std::vector<CharSourceRange> LabelRanges;
   for (ParamDecl *Param: *PL) {
      if (Param->isImplicit())
         continue;

      SourceLoc LabelStart;
      if (auto *repr = Param->getTypeRepr())
         LabelStart = repr->getLoc();
      SourceLoc LabelEnd(LabelStart);

      if (Param->getNameLoc().isValid()) {
         LabelStart = Param->getNameLoc();
      }
      LabelRanges.push_back(CharSourceRange(SM, LabelStart, LabelEnd));
   }
   return LabelRanges;
}

bool NameMatcher::handleCustomAttrs(Decl *D) {
   // CustomAttrs of non-param VarDecls are handled when this method is called
   // on their containing PatternBindingDecls (see below).
   if (isa<VarDecl>(D) && !isa<ParamDecl>(D))
      return true;

   if (auto *PBD = dyn_cast<PatternBindingDecl>(D)) {
      if (auto *SingleVar = PBD->getSingleVar()) {
         D = SingleVar;
      } else {
         return true;
      }
   }

   for (auto *customAttr : D->getAttrs().getAttributes<CustomAttr, true>()) {
      if (shouldSkip(customAttr->getRangeWithAt()))
         continue;
      auto *Arg = customAttr->getArg();
      if (auto *Repr = customAttr->getTypeLoc().getTypeRepr()) {
         // Note the associated call arguments of the semantic initializer call
         // in case we're resolving an explicit initializer call within the
         // CustomAttr's type, e.g. on `Wrapper` in `@Wrapper(wrappedValue: 10)`.
         POLAR_DEFER { CustomAttrArg = None; };
         if (Arg && !Arg->isImplicit())
            CustomAttrArg = {Repr->getLoc(), Arg};
         if (!Repr->walk(*this))
            return false;
      }
      if (Arg && !Arg->isImplicit()) {
         if (!Arg->walk(*this))
            return false;
      }
   }
   return !isDone();
}

bool NameMatcher::walkToDeclPre(Decl *D) {
   // Handle occurrences in any preceding doc comments
   RawComment R = D->getRawComment();
   if (!R.isEmpty()) {
      for(SingleRawComment C: R.Comments) {
         while(!shouldSkip(C.Range))
            tryResolve(AstWalker::ParentTy(), nextLoc());
      }
   }

   // FIXME: Even implicit Decls should have proper ranges if they include any
   // non-implicit children (fix implicit Decls created for lazy vars).
   if (D->isImplicit())
      return !isDone();

   if (shouldSkip(D->getSourceRangeIncludingAttrs()))
      return false;

   if (!handleCustomAttrs(D))
      return false;

   if (auto *ICD = dyn_cast<IfConfigDecl>(D)) {
      for (auto Clause : ICD->getClauses()) {
         if (!Clause.isActive)
            ++InactiveConfigRegionNestings;

         for (auto Member : Clause.Elements) {
            Member.walk(*this);
         }

         if (!Clause.isActive) {
            assert(InactiveConfigRegionNestings > 0);
            --InactiveConfigRegionNestings;
         }
      }
      return false;
   } else if (AbstractFunctionDecl *AFD = dyn_cast<AbstractFunctionDecl>(D)) {
      std::vector<CharSourceRange> LabelRanges;
      if (AFD->getNameLoc() == nextLoc()) {
         auto ParamList = AFD->getParameters();
         LabelRanges = getLabelRanges(ParamList, getSourceMgr());
      }
      tryResolve(AstWalker::ParentTy(D), D->getLoc(), LabelRangeType::Param,
                 LabelRanges);
   } else if (SubscriptDecl *SD = dyn_cast<SubscriptDecl>(D)) {
      tryResolve(AstWalker::ParentTy(D), D->getLoc(), LabelRangeType::NoncollapsibleParam,
                 getLabelRanges(SD->getIndices(), getSourceMgr()));
   } else if (EnumElementDecl *EED = dyn_cast<EnumElementDecl>(D)) {
      if (auto *ParamList = EED->getParameterList()) {
         auto LabelRanges = getEnumParamListInfo(getSourceMgr(), ParamList);
         tryResolve(AstWalker::ParentTy(D), D->getLoc(), LabelRangeType::CallArg,
                    LabelRanges);
      } else {
         tryResolve(AstWalker::ParentTy(D), D->getLoc());
      }
   } else if (ImportDecl *ID = dyn_cast<ImportDecl>(D)) {
      for(const ImportDecl::AccessPathElement &Element: ID->getFullAccessPath()) {
         tryResolve(AstWalker::ParentTy(D), Element.second);
         if (isDone())
            break;
      }
   } else if (isa<ValueDecl>(D) || isa<ExtensionDecl>(D) ||
              isa<PrecedenceGroupDecl>(D)) {
      tryResolve(AstWalker::ParentTy(D), D->getLoc());
   }
   return !isDone();
}

bool NameMatcher::walkToDeclPost(Decl *D) {
   return !isDone();
}

std::pair<bool, Stmt *> NameMatcher::walkToStmtPre(Stmt *S) {
   // FIXME: Even implicit Stmts should have proper ranges that include any
   // non-implicit Stmts (fix Stmts created for lazy vars).
   if (!S->isImplicit() && shouldSkip(S->getSourceRange()))
      return std::make_pair(false, isDone()? nullptr : S);
   return std::make_pair(true, S);
}

Stmt *NameMatcher::walkToStmtPost(Stmt *S) {
   if (isDone())
      return nullptr;
   return S;
}

std::pair<bool, Expr*> NameMatcher::walkToExprPre(Expr *E) {
   if (shouldSkip(E))
      return std::make_pair(false, isDone()? nullptr : E);
   // @todo
//   if (isa<ObjCSelectorExpr>(E)) {
//      ++SelectorNestings;
//   }

   // only match name locations of expressions apparent in the original source
   if (!E->isImplicit()) {
      // Try to resolve against the below kinds *before* their children are
      // visited to ensure visitation happens in source order.
      switch (E->getKind()) {
         case ExprKind::UnresolvedMember: {
            auto UME = cast<UnresolvedMemberExpr>(E);
            tryResolve(AstWalker::ParentTy(E), UME->getNameLoc(), UME->getArgument(), !UME->getArgument());
         } break;
         case ExprKind::DeclRef: {
            auto DRE = cast<DeclRefExpr>(E);
            tryResolve(AstWalker::ParentTy(E), DRE->getNameLoc(), nullptr, true);
            break;
         }
         case ExprKind::UnresolvedDeclRef: {
            auto UDRE = cast<UnresolvedDeclRefExpr>(E);
            tryResolve(AstWalker::ParentTy(E), UDRE->getNameLoc(), nullptr, true);
            break;
         }
         case ExprKind::StringLiteral:
            // Handle multple locations in a single string literal
            do {
               tryResolve(AstWalker::ParentTy(E), nextLoc());
            } while (!shouldSkip(E));
            break;
         case ExprKind::Subscript: {
            auto SubExpr = cast<SubscriptExpr>(E);
            // visit and check in source order
            if (!SubExpr->getBase()->walk(*this))
               return {false, nullptr};

            auto Labels = getCallArgLabelRanges(getSourceMgr(), SubExpr->getIndex(),
                                                LabelRangeEndAt::BeforeElemStart);
            tryResolve(AstWalker::ParentTy(E), E->getLoc(), LabelRangeType::CallArg, Labels);
            if (isDone())
               break;
            if (!SubExpr->getIndex()->walk(*this))
               return {false, nullptr};

            // We already visited the children.
            if (!walkToExprPost(E))
               return {false, nullptr};
            return {false, E};
         }
         case ExprKind::Tuple: {
            TupleExpr *T = cast<TupleExpr>(E);
            // Handle arg label locations (the index reports property occurrences
            // on them for memberwise inits)
            for (unsigned i = 0, e = T->getNumElements(); i != e; ++i) {
               auto Name = T->getElementName(i);
               if (!Name.empty()) {
                  tryResolve(AstWalker::ParentTy(E), T->getElementNameLoc(i));
                  if (isDone())
                     break;
               }
               if (auto *Elem = T->getElement(i)) {
                  if (!Elem->walk(*this))
                     return {false, nullptr};
               }
            }
            // We already visited the children.
            if (!walkToExprPost(E))
               return {false, nullptr};
            return {false, E};
         }
         case ExprKind::Binary: {
            BinaryExpr *BinE = cast<BinaryExpr>(E);
            // Visit in source order.
            if (!BinE->getArg()->getElement(0)->walk(*this))
               return {false, nullptr};
            if (!BinE->getFn()->walk(*this))
               return {false, nullptr};
            if (!BinE->getArg()->getElement(1)->walk(*this))
               return {false, nullptr};

            // We already visited the children.
            if (!walkToExprPost(E))
               return {false, nullptr};
            return {false, E};
         }
         default: // ignored
            break;
      }
   }
   return std::make_pair(!isDone(), isDone()? nullptr : E);
}

Expr *NameMatcher::walkToExprPost(Expr *E) {
   if (isDone())
      return nullptr;

   if (!E->isImplicit()) {
      // Try to resolve against the below kinds *after* their children have been
      // visited to ensure visitation happens in source order.
      switch (E->getKind()) {
         case ExprKind::MemberRef:
            tryResolve(AstWalker::ParentTy(E), E->getLoc());
            break;
         case ExprKind::UnresolvedDot: {
            auto UDE = cast<UnresolvedDotExpr>(E);
            tryResolve(AstWalker::ParentTy(E), UDE->getNameLoc(), nullptr, true);
            break;
         }
         default:
            break;
      }
   }
   // @todo
//   if (isa<ObjCSelectorExpr>(E)) {
//      assert(SelectorNestings > 0);
//      --SelectorNestings;
//   }

   return E;
}

bool NameMatcher::walkToTypeLocPre(TypeLoc &TL) {
   if (isDone() || shouldSkip(TL.getSourceRange()))
      return false;
   return true;
}

bool NameMatcher::walkToTypeLocPost(TypeLoc &TL) {
   return !isDone();
}

bool NameMatcher::walkToTypeReprPre(TypeRepr *T) {
   if (isDone() || shouldSkip(T->getSourceRange()))
      return false;

   if (isa<ComponentIdentTypeRepr>(T)) {
      // If we're walking a CustomAttr's type we may have an associated call
      // argument to resolve with from its semantic initializer.
      if (CustomAttrArg.hasValue() && CustomAttrArg->first == T->getLoc()) {
         tryResolve(AstWalker::ParentTy(T), T->getLoc(), LabelRangeType::CallArg,
                    getCallArgLabelRanges(getSourceMgr(), CustomAttrArg->second, LabelRangeEndAt::BeforeElemStart));
      } else {
         tryResolve(AstWalker::ParentTy(T), T->getLoc());
      }
   }
   return !isDone();
}

bool NameMatcher::walkToTypeReprPost(TypeRepr *T) {
   return !isDone();
}

std::pair<bool, Pattern*> NameMatcher::walkToPatternPre(Pattern *P) {
   if (isDone() || shouldSkip(P->getSourceRange()))
      return std::make_pair(false, P);

   tryResolve(AstWalker::ParentTy(P), P->getStartLoc());
   return std::make_pair(!isDone(), P);
}

bool NameMatcher::checkComments() {
   if (isDone())
      return false;
   TokensToCheck = TokensToCheck.drop_while([this](const Token &tok) -> bool {
      return getSourceMgr().isBeforeInBuffer(tok.getRange().getEnd(), nextLoc());
   });
   if (TokensToCheck.empty())
      return false;

   const Token &next = TokensToCheck.front();
   if (next.is(polar::tok::comment) && next.getRange().contains(nextLoc()) &&
       !next.getText().startswith("///"))
      return tryResolve(AstWalker::ParentTy(), nextLoc());
   return false;
}

void NameMatcher::skipLocsBefore(SourceLoc Start) {
   while (!isDone() && getSourceMgr().isBeforeInBuffer(nextLoc(), Start)) {
      if (!checkComments()) {
         LocsToResolve.pop_back();
         ResolvedLocs.push_back({AstWalker::ParentTy(), CharSourceRange(), {},
                                 LabelRangeType::None, isActive(), isInSelector()});
      }
   }
}

bool NameMatcher::shouldSkip(Expr *E) {
   if (isa<StringLiteralExpr>(E) && Parent.getAsExpr()) {
      // Attempting to get the CharSourceRange from the SourceRange of a
      // StringLiteralExpr that is a segment of an interpolated string gives
      // incorrect ranges. Use the CharSourceRange of the corresponding token
      // instead.

      auto ExprStart = E->getStartLoc();
      auto RemaingTokens = TokensToCheck.drop_while([&](const Token &tok) -> bool {
         return getSourceMgr().isBeforeInBuffer(tok.getRange().getStart(), ExprStart);
      });

      if (!RemaingTokens.empty() && RemaingTokens.front().getLoc() == ExprStart)
         return shouldSkip(RemaingTokens.front().getRange());
   }
   return shouldSkip(E->getSourceRange());
}

bool NameMatcher::shouldSkip(SourceRange Range) {
   return shouldSkip(Lexer::getCharSourceRangeFromSourceRange(getSourceMgr(),
                                                              Range));
}

bool NameMatcher::shouldSkip(CharSourceRange Range) {
   if (isDone())
      return true;
   if (Range.isInvalid())
      return false;

   skipLocsBefore(Range.getStart());
   return isDone() || !Range.contains(nextLoc());
}

SourceLoc NameMatcher::nextLoc() const {
   assert(!LocsToResolve.empty());
   return LocsToResolve.back().Loc;
}

std::vector<CharSourceRange> getSelectorLabelRanges(SourceManager &SM,
                                                    DeclNameLoc NameLoc) {
   SourceLoc Loc;
   std::vector<CharSourceRange> Ranges;
   size_t index = 0;
   while((Loc = NameLoc.getArgumentLabelLoc(index++)).isValid()) {
      CharSourceRange Range = Lexer::getCharSourceRangeFromSourceRange(SM,
                                                                       SourceRange(Loc));
      Ranges.push_back(Range);
   }

   return Ranges;
}

bool NameMatcher::tryResolve(AstWalker::ParentTy Node, DeclNameLoc NameLoc,
                             Expr *Arg, bool checkParentForLabels) {
   if (NameLoc.isInvalid())
      return false;

   if (NameLoc.isCompound()) {
      auto Labels = getSelectorLabelRanges(getSourceMgr(), NameLoc);
      bool Resolved = tryResolve(Node, NameLoc.getBaseNameLoc(),
                                 LabelRangeType::Selector, Labels);
      if (!isDone()) {
         for (auto Label: Labels) {
            if (tryResolve(Node, Label.getStart())) {
               Resolved = true;
               if (isDone())
                  break;
            }
         }
      }
      return Resolved;
   }

   if (LocsToResolve.back().ResolveArgLocs) {
      if (Arg)
         return tryResolve(Node, NameLoc.getBaseNameLoc(), LabelRangeType::CallArg,
                           getCallArgLabelRanges(getSourceMgr(), Arg,
                                                 LabelRangeEndAt::BeforeElemStart));

      if (checkParentForLabels) {
         if (auto P = dyn_cast_or_null<ApplyExpr>(Parent.getAsExpr())) {
            if (P->getFn() == Node.getAsExpr())
               return tryResolve(Node, NameLoc.getBaseNameLoc(),
                                 LabelRangeType::CallArg,
                                 getCallArgLabelRanges(getSourceMgr(), P->getArg(),
                                                       LabelRangeEndAt::BeforeElemStart));
         }
      }
   }

   return tryResolve(Node, NameLoc.getBaseNameLoc());
}

bool NameMatcher::tryResolve(AstWalker::ParentTy Node, SourceLoc NameLoc) {
   assert(!isDone());
   return tryResolve(Node, NameLoc, LabelRangeType::None, None);
}

bool NameMatcher::tryResolve(AstWalker::ParentTy Node, SourceLoc NameLoc,
                             LabelRangeType RangeType,
                             ArrayRef<CharSourceRange> LabelRanges) {
   skipLocsBefore(NameLoc);
   if (isDone())
      return false;

   CharSourceRange Range = Lexer::getCharSourceRangeFromSourceRange(getSourceMgr(),
                                                                    NameLoc);
   UnresolvedLoc &Next = LocsToResolve.back();
   bool WasResolved = false;
   if (Range.isValid()) {
      if (NameLoc == Next.Loc) {
         LocsToResolve.pop_back();
         ResolvedLocs.push_back({Node, Range, LabelRanges, RangeType,
                                 isActive(), isInSelector()});
         if (isDone())
            return true;
         WasResolved = true;
      }

      if (Range.getByteLength() > 1 &&
          (Range.str().front() == '_' || Range.str().front() == '$')) {
         // Also try after any leading _ or $ for name references of wrapped
         // properties, e.g. 'foo' in '_foo' and '$foo' occurrences.
         auto NewRange = CharSourceRange(Range.getStart().getAdvancedLoc(1),
                                         Range.getByteLength() - 1);
         if (NewRange.getStart() == Next.Loc) {
            LocsToResolve.pop_back();
            ResolvedLocs.push_back({Node, NewRange, {}, LabelRangeType::None,
                                    isActive(), isInSelector()});
            WasResolved = true;
         }
      }
   }
   return WasResolved;
}

void ResolvedRangeInfo::print(llvm::raw_ostream &OS) const {
   OS << "<Kind>";
   switch (Kind) {
      case RangeKind::SingleExpression: OS << "SingleExpression"; break;
      case RangeKind::SingleDecl: OS << "SingleDecl"; break;
      case RangeKind::MultiTypeMemberDecl: OS << "MultiTypeMemberDecl"; break;
      case RangeKind::MultiStatement: OS << "MultiStatement"; break;
      case RangeKind::PartOfExpression: OS << "PartOfExpression"; break;
      case RangeKind::SingleStatement: OS << "SingleStatement"; break;
      case RangeKind::Invalid: OS << "Invalid"; break;
   }
   OS << "</Kind>\n";

   OS << "<Content>" << ContentRange.str() << "</Content>\n";

   if (auto Ty = getType()) {
      OS << "<Type>";
      Ty->print(OS);
      OS << "</Type>";
      switch(exit()) {
         case ExitState::Positive: OS << "<Exit>true</Exit>"; break;
         case ExitState::Unsure: OS << "<Exit>unsure</Exit>"; break;
         case ExitState::Negative: OS << "<Exit>false</Exit>"; break;
      }
      OS << "\n";
   }

   if (RangeContext) {
      OS << "<Context>";
      printContext(OS, RangeContext);
      OS << "</Context>\n";
   }

   if (CommonExprParent) {
      OS << "<Parent>";
      OS << Expr::getKindName(CommonExprParent->getKind());
      OS << "</Parent>\n";
   }

   if (!HasSingleEntry) {
      OS << "<Entry>Multi</Entry>\n";
   }

   if (ThrowingUnhandledError) {
      OS << "<Error>Throwing</Error>\n";
   }

   if (Orphan != OrphanKind::None) {
      OS << "<Orphan>";
      switch (Orphan) {
         case OrphanKind::Continue:
            OS << "Continue";
            break;
         case OrphanKind::Break:
            OS << "Break";
            break;
         case OrphanKind::None:
            llvm_unreachable("cannot enter here.");
      }
      OS << "</Orphan>";
   }

   for (auto &VD : DeclaredDecls) {
      OS << "<Declared>" << VD.VD->getBaseName() << "</Declared>";
      OS << "<OutscopeReference>";
      if (VD.ReferredAfterRange)
         OS << "true";
      else
         OS << "false";
      OS << "</OutscopeReference>\n";
   }
   for (auto &RD : ReferencedDecls) {
      OS << "<Referenced>" << RD.VD->getBaseName() << "</Referenced>";
      OS << "<Type>";
      RD.Ty->print(OS);
      OS << "</Type>\n";
   }

   OS << "<ASTNodes>" << ContainedNodes.size() << "</ASTNodes>\n";
   OS << "<end>\n";
}

CharSourceRange ResolvedRangeInfo::
calculateContentRange(ArrayRef<Token> Tokens) {
   if (Tokens.empty())
      return CharSourceRange();
   auto StartTok = Tokens.front();
   auto EndTok = Tokens.back();
   auto StartLoc = StartTok.hasComment() ?
                   StartTok.getCommentStart() : StartTok.getLoc();
   auto EndLoc = EndTok.getRange().getEnd();
   auto Length = static_cast<const char *>(EndLoc.getOpaquePointerValue()) -
                 static_cast<const char *>(StartLoc.getOpaquePointerValue());
   return CharSourceRange(StartLoc, Length);
}

bool DeclaredDecl::operator==(const DeclaredDecl& Other) {
   return VD == Other.VD;
}

ReturnInfo::
ReturnInfo(AstContext &Ctx, ArrayRef<ReturnInfo> Branches):
   ReturnType(Ctx.TheErrorType.getPointer()), Exit(ExitState::Unsure) {
   std::set<TypeBase*> AllTypes;
   std::set<ExitState> AllExitStates;
   for (auto I : Branches) {
      AllTypes.insert(I.ReturnType);
      AllExitStates.insert(I.Exit);
   }
   if (AllTypes.size() == 1) {
      ReturnType = *AllTypes.begin();
   }
   if (AllExitStates.size() == 1) {
      Exit = *AllExitStates.begin();
   }
}

void polar::ide::getLocationInfoForClangNode(ClangNode ClangNode,
                                             ClangImporter *Importer,
                                             llvm::Optional<std::pair<unsigned, unsigned>> &DeclarationLoc,
                                             StringRef &Filename) {
   clang::ASTContext &ClangCtx = Importer->getClangAstContext();
   clang::SourceManager &ClangSM = ClangCtx.getSourceManager();

   clang::SourceRange SR = ClangNode.getLocation();
   if (auto MD = dyn_cast_or_null<clang::ObjCMethodDecl>(ClangNode.getAsDecl())) {
      SR = clang::SourceRange(MD->getSelectorStartLoc(),
                              MD->getDeclaratorEndLoc());
   }

   clang::CharSourceRange CharRange =
      clang::Lexer::makeFileCharRange(clang::CharSourceRange::getTokenRange(SR),
                                      ClangSM, ClangCtx.getLangOpts());
   if (CharRange.isInvalid())
      return;

   std::pair<clang::FileID, unsigned>
      Decomp = ClangSM.getDecomposedLoc(CharRange.getBegin());
   if (!Decomp.first.isInvalid()) {
      if (auto FE = ClangSM.getFileEntryForID(Decomp.first)) {
         Filename = FE->getName();

         std::pair<clang::FileID, unsigned>
            EndDecomp = ClangSM.getDecomposedLoc(CharRange.getEnd());

         DeclarationLoc = { Decomp.second, EndDecomp.second-Decomp.second };
      }
   }
}

static unsigned getCharLength(SourceManager &SM, SourceRange TokenRange) {
   SourceLoc CharEndLoc = Lexer::getLocForEndOfToken(SM, TokenRange.end);
   return SM.getByteDistance(TokenRange.start, CharEndLoc);
}

void polar::ide::getLocationInfo(const ValueDecl *VD,
                                 llvm::Optional<std::pair<unsigned, unsigned>> &DeclarationLoc,
                                 StringRef &Filename) {
   AstContext &Ctx = VD->getAstContext();
   SourceManager &SM = Ctx.SourceMgr;

   auto ClangNode = VD->getClangNode();

   if (VD->getLoc().isValid()) {
      unsigned NameLen;
      if (auto FD = dyn_cast<AbstractFunctionDecl>(VD)) {
         SourceRange R = FD->getSignatureSourceRange();
         if (R.isInvalid())
            return;
         NameLen = getCharLength(SM, R);
      } else {
         if (VD->hasName()) {
            NameLen = VD->getBaseName().userFacingName().size();
         } else {
            NameLen = getCharLength(SM, VD->getLoc());
         }
      }

      unsigned DeclBufID = SM.findBufferContainingLoc(VD->getLoc());
      DeclarationLoc = { SM.getLocOffsetInBuffer(VD->getLoc(), DeclBufID),
                         NameLen };
      Filename = SM.getIdentifierForBuffer(DeclBufID);

   } else if (ClangNode) {
      ClangImporter *Importer =
         static_cast<ClangImporter*>(Ctx.getClangModuleLoader());
      return getLocationInfoForClangNode(ClangNode, Importer,
                                         DeclarationLoc, Filename);
   }
}

CharSourceRange CallArgInfo::getEntireCharRange(const SourceManager &SM) const {
   return CharSourceRange(SM, LabelRange.getStart(),
                          Lexer::getLocForEndOfToken(SM, ArgExp->getEndLoc()));
}

static Expr* getSingleNonImplicitChild(Expr *Parent) {
   // If this expr is non-implicit, we are done.
   if (!Parent->isImplicit())
      return Parent;

   // Collect all immediate children.
   llvm::SmallVector<Expr*, 4> Children;
   Parent->forEachImmediateChildExpr([&](Expr *E) {
      Children.push_back(E);
      return E;
   });

   // If more than one children are found, we are not sure the non-implicit node.
   if (Children.size() != 1)
      return Parent;

   // Dig deeper if necessary.
   return getSingleNonImplicitChild(Children[0]);
}

std::vector<CallArgInfo> polar::ide::
getCallArgInfo(SourceManager &SM, Expr *Arg, LabelRangeEndAt EndKind) {
   std::vector<CallArgInfo> InfoVec;
   if (auto *TE = dyn_cast<TupleExpr>(Arg)) {
      size_t ElemIndex = 0;
      for (Expr *Elem : TE->getElements()) {
         SourceLoc LabelStart(Elem->getStartLoc());
         SourceLoc LabelEnd(LabelStart);

         auto NameIdentifier = TE->getElementName(ElemIndex);
         if (!NameIdentifier.empty()) {
            LabelStart = TE->getElementNameLoc(ElemIndex);
            if (EndKind == LabelRangeEndAt::LabelNameOnly)
               LabelEnd = LabelStart.getAdvancedLoc(NameIdentifier.getLength());
         }
         bool IsTrailingClosure = TE->hasTrailingClosure() &&
                                  ElemIndex == TE->getNumElements() - 1;
         InfoVec.push_back({getSingleNonImplicitChild(Elem),
                            CharSourceRange(SM, LabelStart, LabelEnd), IsTrailingClosure});
         ++ElemIndex;
      }
   } else if (auto *PE = dyn_cast<ParenExpr>(Arg)) {
      if (auto Sub = PE->getSubExpr())
         InfoVec.push_back({getSingleNonImplicitChild(Sub),
                            CharSourceRange(Sub->getStartLoc(), 0),
                            PE->hasTrailingClosure()
                           });
   }
   return InfoVec;
}

std::vector<CharSourceRange> polar::ide::
getCallArgLabelRanges(SourceManager &SM, Expr *Arg, LabelRangeEndAt EndKind) {
   std::vector<CharSourceRange> Ranges;
   auto InfoVec = getCallArgInfo(SM, Arg, EndKind);

   auto EndWithoutTrailing = std::remove_if(InfoVec.begin(), InfoVec.end(),
                                            [](CallArgInfo &Info) {
                                               return Info.IsTrailingClosure;
                                            });
   std::transform(InfoVec.begin(), EndWithoutTrailing,
                  std::back_inserter(Ranges),
                  [](CallArgInfo &Info) { return Info.LabelRange; });
   return Ranges;
}
